package wh.F的圣诞树;

import javax.sound.sampled.LineUnavailableException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/12/23 15:55
 * @description:
 * @version:
 */
public class Solution {

    //根据数组来创建二叉树，不止可以创建完全二叉树
    public static TreeNode createTree(Integer[] arr) {
        // 使用队列来存储每一层的非空节点，下一层的数目要比上一层高
        ArrayDeque<TreeNode> pre = new ArrayDeque<>();
        TreeNode root = new TreeNode(arr[0]);
        pre.addLast(root);
        // 表示要遍历的下一个节点
        int index = 0;
        //记录当前层次的深度
        int depth = 0;
        List<Integer> list = new ArrayList<>();
        list.add(depth);
        while (!pre.isEmpty()) {
            ArrayDeque<TreeNode> cur = new ArrayDeque<>();
            while (!pre.isEmpty()) {
                TreeNode node = pre.removeFirst();
                TreeNode left=null;
                TreeNode right=null;
                // 如果对应索引上的数组不为空的话就创建一个节点,进行判断的时候，
                // 要先索引看是否已经超过数组的长度，如果索引已经超过了数组的长度，那么list = {ArrayList@546}  size = 6剩下节点的左右子节点就都是空了
                // 这里index每次都会增加，实际上是不必要的，但是这样写比较简单
                if (++index<arr.length&&arr[index]!=null){
                    left=new TreeNode(arr[index]);
                    cur.addLast(left);
                    list.add(depth + 1);
                }else {
                    list.add(-1);
                }
                if (++index<arr.length&&arr[index]!=null){
                    right=new TreeNode(arr[index]);
                    cur.addLast(right);
                    list.add(depth + 1);
                }else list.add(-1);
                node.left=left;
                node.right=right;
            }
            pre=cur;
            depth++;
        }

        int countSum = 0;
        //求出相互作用之和 list存储的是对应的节点的层次
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                int maxCount = arr[i]>arr[j] ? arr[i] : arr[j];
                countSum += maxCount*(list.get(i) + list.get(j));
            }
        }
        System.out.println("所求结果的相互作用之和为"+ countSum);

        return root;
    }

    public static void main(String[] args) {
        Integer[] arr = {1,1,4,5,1,4};
        //Integer[] arr={5,4};
        TreeNode tree = createTree(arr);
      //  prePrinTree(tree);

    }
    //中序遍历
    private static void prePrinTree(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + " ");
        prePrinTree(node.left);
        prePrinTree(node.right);
    }
}

